#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>

using namespace std;

//class Solution1314 {
//public:
//    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
///*       vector<vector<int>> ret, dp;
//
//        dp.resize(mat.size() + 1);
//        for (int i = 0; i < mat.size() + 1; i++) {
//            dp[i].resize(mat[0].size() + 1);
//            for (int j = 0; j < mat[0].size() + 1; j++) {
//                dp[i][j] = 0;
//            }
//        }*/
//        int m = mat.size(), n = mat[1].size();
//        vector<vector<int>> ret;
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//
//        for (int i = 1; i < mat.size() + 1; i++) {
//            for (int j = 1; j < mat[0].size() + 1; j++) {
//                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
//            }
//        }
//
//        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
//        for (int i = 0; i < mat.size(); i++) {
//            vector<int> v;
//            for (int j = 0; j < mat[0].size(); j++) {
//                x1 = max(0, i - k) + 1;
//                y1 = max(0, j - k) + 1;
//                x2 = min((int)mat.size() - 1, i + k) + 1;
//                y2 = min((int)mat[0].size() - 1, j + k) + 1;
//                int sum = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
//                v.push_back(sum);
//            }
//            ret.emplace_back(v);
//        }
//
//        return ret;
//    }
//};

class Solution1314 {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[1].size();
        vector<vector<int>> ret;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] +
                    mat[i - 1][j - 1];
            }
        }

        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        for (int i = 0; i < m; i++) {
            vector<int> v;
            for (int j = 0; j < n; j++) {
                x1 = max(0, i - k) + 1;
                y1 = max(0, j - k) + 1;
                x2 = min(m - 1, i + k) + 1;
                y2 = min(n - 1, j + k) + 1;
                int sum = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +
                    dp[x1 - 1][y1 - 1];
                v.push_back(sum);
            }
            ret.emplace_back(v);
        }

        return ret;
    }
};
class Solution9 {
public:
    bool isPalindrome1(int x) {
        string s = to_string(x);
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l++] != s[r--])
                return false;
        }
        return true;
    }
    //bool isPalindrome(int x) {
    //    if (x < 0 || (x > 0 && x % 10 == 0)) return false;
    //    int rn = 0;
    //    while (rn < x) {
    //        rn *= 10;
    //        rn += x % 10;
    //        x /= 10;
    //    }
    //    if (rn > x) rn /= 10;
    //    return rn == x;
    //}
    bool isPalindrome(int x) {
        if (x < 0 || (x > 0 && x % 10 == 0))
            return false;

        int rn = 0;
        while (rn < x) {
            rn = rn * 10 + x % 10;
            x /= 10;
        }

        return x == rn || x == (rn / 10);
    }
};

class Solution2081{
public:
    bool is_palindrome(long long x, int k) {
        if (x % k == 0) {
            return false;
        }
        long long reversed = 0, original = x;
        while (x > 0) {
            reversed = reversed * k + x % k;
            x /= k;
        }
        return reversed == original;
    }
    long long kMirror(int k, int n) {
        int ct = 0, left = 1;
        long long ret = 0;
        while (ct < n) {
            int right = left * 10;
            for (int flag = 0; flag < 2; flag++) {
                for (int i = left; i < right && ct < n; i++) {
                    long long t = i;
                    int x = (flag == 0 ? i / 10 : i);
                    while (x) {
                        t = t * 10 + x % 10;
                        x /= 10;
                    }
                    if (is_palindrome(t, k)) {
                        ct++;
                        ret += t;
                    }
                }
            }
            left = right;
        }

        return ret;
    }
};
int main()
{
    Solution1314 s;
    vector<vector<int>> mat = { {1,2,3},{4,5,6},{7,8,9} };
    int k = 1;
    vector<vector<int>> result = s.matrixBlockSum(mat, k);
    for (const auto& row : result) {
        for (const auto& val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}